package com.leetcode.LC_MED;

import java.util.Arrays;
import java.util.Comparator;

public class LC435 {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));

        int len = intervals.length;
        // points 不为空至少需要一支箭
        int count = 1;
        for (int i = 1; i < len; i++) {
            if (intervals[i - 1][1] <= intervals[i][0]) {
                // 需要一支箭
                count++;
            } else {
                // 气球i和气球i-1挨着
                // 更新重叠气球最小右边界
                intervals[i][1] = Math.min(intervals[i - 1][1], intervals[i][1]);
            }
        }
        return len - count;
    }
}
